This invention relates in general to the field of Raster Image Processing, and more specifically to a feedback approach that automatically controls the image compression ratios required to minimize the memory requirements for Raster Image Processors employed in generating a bitmap representation of a composite page.
When printing a document, the page to be printed is typically composed electronically using software like QuarkXpress, Framemaker, etc. Internally the page is stored in a vector based graphical representation by these composition tools. Before display or printing, the vector-based representation of the page is converted to a bitmap representation at the desired resolution by a process called Rasterisation.
This conversion process can usually be divided into two stages: interpretation and rendering. Interpretation is the process where the original page description is reduced to a series of drawing primitives called the display list. Rendering is the process where these drawing primitives are converted to a bitmap in the frame buffer.
At high resolutions, a significant amount of memory is required to store this bitmap image. As an example, an 8.5xe2x80x3xc3x9711xe2x80x3 page at a resolution of 600 Dots per Inch (dpi), 8 bits/pixel and 4 color planes will require 128 MB of frame buffer memory.
If the available frame buffer memory is less than this limit, an alternate strategy must be followed. The page is divided into smaller portions or bands, with the band size being determined by the available frame buffer memory. Each band is then rendered to bitmap form and passed on to the exposure, printing or display module to make space for the subsequent bands.
Since the exposure module has to be fed with bitmap data at regular intervals, each band must be rendered in a predefined time. As rendering is computationally intensive, such real-time rendering may not be possible for some complex bands. If this is the case, each band must be pre-rendered, compressed and stored. After all the bands have been processed and compressed, they are decompressed in real time and fed to the exposure module.
In some cases real-time rendering may not be possible even though the bands are not complex. If the available memory is limited, there may not be sufficient room to store the original display list and other information required for rendering the page.
There are various methods that may be employed to compress the rendered image. To maintain maximum image quality, a lossless or low loss method is preferred. Unfortunately, the amount of compression attainable with most of these methods is highly dependent on the page content, and some pages will compress much more than others. Since the amount of memory and the page size are fixed, a method must be found to guarantee that all pages can be rendered and printed in real time.
This invention shows a feedback algorithm designed to select and enforce a target compression ratio that will guarantee that the system will be capable of rendering any input page, irrespective of the complexity, within the available memory limitations.
The feedback methods shown apply to a block-based, hybrid compression method. The image to be rendered is first segmented into non-overlapping blocks of pixels. Each block is then classified as Solids, Text (saturated or unsaturated), or image areas. The compression method applied to each block is then selected based on the class of the block, according to the following criteria:
Differential Pulse Code Modulation (DPCM) is used to code solids
Block Truncation Coding (BTC) is used for text
Image blocks may be coded using DPCM, DCT (Discrete Cosine
Transform), BTC or a combination of these methods. The image blocks may also be decimated previous to coding.
Runs of repeating solids are compressed using run length coding.
The highest compression ratio is achieved using DPCM on blocks classified as solids. Accordingly, adjusting the threshold used in classifying the blocks as solids will modulate the effective compression ratio, and by increasing the number of solids the compression ratio is also increased.
If the target compression ratio is not met by using the feedback mechanism, a fall back strategy may be employed. In this case, the entire band must be decimated by 2:1, followed by BTC. Since decimated bands do not visibly stand out from other bands that have not been decimated, this decision may be made on a band by band basis.
The feedback compression approach shown can be very efficiently implemented on a parallel processor such as the Texas Instruments TMS320C80 family.